﻿#define _CRT_SECURE_NO_WARNINGS 1

#include"SinglyList.h"

//获取节点
static SLNode* GetNode(SListDataType data)
{
	SLNode* node = (SLNode*)malloc(sizeof(SLNode));
	if (node == NULL)
	{
		perror("GetNode Malloc");
		exit(-1);
	}
	node->data = data;
	node->next = NULL;

	return node;
}

void SLPrint(const SLNode** pphead)
{
	assert(pphead);

	const SLNode* cur = *pphead;
	while (cur != NULL)
	{
		printf("%d -> ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}


//头插
void SLPustfront(SLNode** pphead, SListDataType data)
{
	assert(pphead);
	//SLNode* node = GetNode(data);
	//if (*pphead == NULL)
	//{
	//	*pphead = node;
	//}
	//else
	//{
	//	node->next = *pphead;
	//	*pphead = node;
	//}

	SLNode* node = GetNode(data);
	if (*pphead == NULL)
	{
		*pphead = node;
	}
	else
	{
		//直接使用SLInsert函数
		SLInsert(pphead, *pphead, data);
	}

}

//头删
void SLPopfront(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	//if ((*pphead)->next == NULL)
	//{
	//	free(*pphead);
	//	*pphead = NULL;
	//}
	//else
	//{
	//	SLNode* cur = *pphead;
	//	*pphead = cur->next;
	//	free(cur);
	//	cur = NULL;
	//}

	SLErase(pphead, *pphead);
}

//尾插
void SLPustBack(SLNode** pphead, SListDataType data)
{
	assert(pphead);
	SLNode* node = GetNode(data);

	//情况1,首次插入
	if ((*pphead) == NULL)
	{
		*pphead = node;
	}
	else
	{
		//情况二，尾部插入
		SLNode* tail = *pphead;
		//找尾节点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = node;
	}
}

//尾删
void SLPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//情况1,z只有一个节点时
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//情况2,有多个节点时进行尾删

		SLNode* tail = *pphead;
		SLNode* pre = *pphead;
		//找尾节点和尾节点的前一个指针
		while (tail->next != NULL)
		{
			pre = tail;
			tail = tail->next;
		}

		pre->next = NULL;
		free(tail);
		tail = NULL;
	}

}

//查找
SLNode* SLFind(SLNode** pphead, SListDataType data)
{
	assert(pphead);
	assert(*pphead);

	SLNode* cur = *pphead;
	while (cur != NULL)
	{
		if (cur->data == data)
		{
			return cur;//找到了
		}

		cur = cur->next;
	}

	return NULL;//没找到
}

//在指定位置之前插⼊数据
void SLInsert(SLNode** pphead, SLNode* pos, SListDataType data)
{
	assert(pphead);
	assert(pos);
	SLNode* node = GetNode(data);

	//情况1，头插
	if ((*pphead) == pos)
	{
		node->next = *pphead;
		*pphead = node;
	}
	else
	{
		//情况2，在pos之前插入
		SLNode* pre = *pphead;
		//找pos的前一个节点
		while (pre->next != pos)
		{
			pre = pre->next;
		}

		pre->next = node;
		node->next = pos;
	}
}

//删除pos结点
void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	//情况1：只有一个节点时
	if (*pphead == pos)
	{
		*pphead = (*pphead)->next;
		free(pos);
		pos = NULL;
		 
	}
	else
	{
		//情况2：在多个节点内删除pos位置的节点
		SLNode* posPre = *pphead;//记录着pos的前一个节点
		SLNode* posTail = pos->next;//记录着pos的后一个节点
		//找pos的前一个节点
		while (posPre->next != pos)
		{
			posPre = posPre->next;
		}
		posPre->next = posTail;
		free(pos);
		pos = NULL;
	}
}


//在指定位置之后插⼊数据
void SLInsertAfter(SLNode* pos, SListDataType data)
{
	assert(pos);

	SLNode* node = GetNode(data);
	//情况1：pos->next指向的是NULL
	if (pos->next == NULL)
	{
		pos->next = node;
	}
	else
	{
		//情况2：pos->next指向的是节点
		SLNode* posTail = pos->next;
		pos->next = node;
		node->next = posTail;
	}
	
}

//删除pos之后的结点
void SLEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);

	SLNode* posNext = pos->next;
	SLNode* posNextNext = pos->next->next;

	pos->next = posNextNext;
	free(posNext);
	posNext = NULL;
}

//链表的销毁
void SLDestroy(SLNode** pphead)
{
	assert(pphead);

	SLNode* cur = *pphead;
	while (cur != NULL)
	{
		SLNode* tmp = cur;
		cur = cur->next;
		free(tmp);
		tmp = NULL;
	}
	
	*pphead = NULL;
}